package com.midea.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LeetCode47 {
    public static void main(String[] args) {
        int[] nums = new int[]{1,1,2};
        System.out.println(permuteUnique(nums));
    }
    public static List<List<Integer>> permuteUnique(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i : nums){
            map.put(i,map.containsKey(i) ? map.get(i)+1 : 1);
        }
        int len = map.size();
        int[] p = new int[len];
        int[] pb = new int[len];
        int index = 0;
        for (Map.Entry<Integer,Integer> entry : map.entrySet() ) {
            p[index] = entry.getKey();
            pb[index] = entry.getValue();
            index++;
        }
        List<List<Integer>> result = new ArrayList<>();
        dfs(nums.length,p,pb,new ArrayList<>(),result);
        return result;
    }

     static void dfs(int size,int[] p,int[] pb,List<Integer> res,List<List<Integer>> result) {
        //截止条件
        if (size == res.size()) {
            List<Integer> temp = new ArrayList<>();
            temp.addAll(res);
            result.add(temp);
            return;
        }
        //候选条件
         for (int i = 0; i < p.length;i++) {
             int c = p[i];
             if (pb[i] > 0) {
                 res.add(c);
                 pb[i]--;
                 dfs(size,p,pb,res,result);
                 res.remove(res.size()-1);
                 pb[i]++;
             }
         }

    }
}
